This invention relates to data compression/decompression and more particularly, to image data compression and decompression. Still more particularly, the present invention relates to run length encoding of patterns and symbols (e.g., characters) to provide efficient and rapid loss-less decompression of character-mapped graphics data within a limited resource environment such as a handheld portable video game system.
The world of video games has been transformed by the increased amount of computing power that can be placed on a single semiconductor integrated circuit chip. Games that just a few years ago were available only on expensive arcade video systems can now be played on inexpensive handheld portable video game systems.
The GAME BOYS(copyright) and GAME BOY COLOR(copyright) portable video game systems sold by Nintendo have become quite popular in recent years. These handheld systems offer impressive interactive video game play in a very compact and inexpensive (less than $100) package. One of the challenges facing game developers for these systems is how to develop increasingly sophisticated and complex games that are fun and interesting and yet operate within the very limited memory and processing resources these systems offer.
As one example, suppose one wants to implement an adventure game on GAME BOY COLOR(copyright). The display memory of GAME BOY COLOR(copyright) stores a background character map that is several (e.g., four to eight) times larger than the screen the liquid crystal display can display at one time. This allows for smooth scrolling of a display xe2x80x9cwindowxe2x80x9d within a larger virtual display area (for example, a landscape or xe2x80x9clevelxe2x80x9d within the adventure game). But suppose one desires to make a very interesting adventure game allowing smooth scrolling within an expansive landscape comprising many hundreds of image screens. The limited display memory of GAME BOY COLOR(copyright) cannot store so many screens worth of image information at one time, and storing this many screens of image information in a game cartridge will require a large amount of read only memory space. One way to solve this problem is to use data compression to transform the image data so it occupies less space.
Because images can take up a lot of storage space, data compression is especially important in computer graphics. Computer scientists have developed a variety of data compression techniques for graphics files. A useful survey of a variety of compression techniques that have been applied to graphics files can be found in Chapter 9 (xe2x80x9cData Compressionxe2x80x9d) of Murray et al, Graphics File Formats (O""Reilly and Associates, 2d Ed. 1996) at pages 153-218.
Generally, two kinds of data compression exist: lossless compression in which no loss of data occurs during compression, and lossy compression, in which some data is lost and is not incorporated in the compressed data. In general, both types of data compression techniques rely on reducing the amount of data redundancy in the compressed image. Data compression is a type of data encoding that is used to reduce the size of the data file. The process of converting recurring characters or patterns into shorter symbols, known as codes, is called encoding. The process of translating codes back into the original characters or patterns is called decoding.
One simple but effective data compression technique commonly used in the past for compressing graphics files is called run length encoding. Run length encoding is supported by many commonly-used bitmap graphics file formats such as, for example, TIFF, BMP and PCX. Run length encoding works by reducing the physical size of a repeating string of symbols (e.g., characters). This repeating string, called a xe2x80x9crunxe2x80x9d, is typically encoded into two bytes. The first byte, called the xe2x80x9crun count,xe2x80x9d represents the number of symbols in the run. The second byte, called the xe2x80x9crun value,xe2x80x9d is the value of the symbol in the run (in the range of 0 to 255 binary for ASCII characters). For example, a character run of 15 xe2x80x9cAxe2x80x9d characters (xe2x80x9cAAAAAAAAAAAAAAAxe2x80x9d) would normally require 15 bytes to store. The same string after run length encoding would require only two bytes: xe2x80x9c15Axe2x80x9d.
Although much data compression work has been done in the past, further improvements are possible. In particular, there is a need for a data compression and decompression technique that has the simplicity, efficiency and low overhead associated with run length encoding techniques, but which is especially suited for character-mapped image and attribute data and allows efficient image decompression in a limited resource system such as a handheld portable video game system.
The present invention provides a new and improved data compression technique that enhances typical run length encoding by examining the input image file and finding the recurrence of symbols as well as recurrence of patterns of symbols that could be represented by shorter symbols. This multi-level compression technique can be implemented quite efficiently using only a small amount of overhead data so that resulting compressed image data can be efficiently decompressed, at run time xe2x80x9con the flyxe2x80x9d, in a processing-and-memory constrained environment such as a compact portable video game system. Such loss-less data compression/decompression is especially useful in a limited resource environment such as a handheld portable video game system, since it allows graphics and/or attribute data to be efficiently and quickly decompressed on an as-needed basis in real time response to interactive user inputs.
In the preferred embodiment, a common xe2x80x9csentinelxe2x80x9d field format encodes whether data following the field is non-redundant data, a symbol run, or a pattern run. Compression ratios of 60% for representative character-mapped video display graphics/attribute files can be achieved.
A data compression method in accordance with one aspect of the invention is characterized by scanning an input file to detect pattern and symbol redundancy; if the scanning step reveals a pattern redundancy, run length encoding said pattern redundancy and writing said run length encoded pattern redundancy to an output file; if the scanning step reveals symbol redundancy, run length encoding said symbol redundancy and writing said run length encoded symbol redundancy to said output file; and if the scanning step reveals neither symbol redundancy nor pattern redundancy, writing non-redundant information to said output file.
A data decompression method is characterized by reading, within an input file, a predetermined data format capable of indicating any of (a) pattern redundancy, and (b) symbol redundancy; if the predetermined data format indicates pattern redundancy, run length decoding a redundant pattern run associated with said predetermined data format; if the predetermined data format indicates symbol redundancy, run length decoding a redundant symbol run associated with said predetermined data format; and if the predetermined data format indicates neither pattern redundancy nor symbol redundancy, reading non-redundant data associated with said predetermined data format.
The predetermined data format may comprise a sentinel field format including a first field indicating redundancy or non-redundancy and a second field indicating the number of redundant symbols if symbol redundancy exists, the value of said first and second fields together being encoded with a predetermined value if the scanning step reveals pattern redundancy.